// hard

// 给定n个非负整数表示每个宽度为1的柱子的高度图，用数组height表示，其中height[i]表示第i根柱子的高度
// 要求计算按此排列的柱子，下雨之后能接多少雨水

// 步骤
// 1. 遍历高度数组height
// 2. 如果当前柱体高度较小，小于等于栈顶柱体的高度，则将当前柱子高度入栈
// 3. 如果当前柱体高度较大，大于栈顶柱体的高度，则一直出栈，直到当前柱体小于等于栈顶柱体的高度
// 4. 假设当前柱体为C，出栈柱体为B，，出栈之后新的栈顶柱体为A，则说明：
//    当前柱体C是出栈柱体B向右找到的第一个大于当前柱体高度的柱体，那么以出栈柱体B为中心，可以向右将宽度扩展到当前柱体C
//    新的栈顶柱体A是出栈柱体B向左找到的第一个大于当前柱体高度的柱体，那么以栈顶柱体B为中心，可以向左将宽度扩展到当前柱体A
// 5. 出栈后，以新的栈顶柱体A为左边界，以当前柱体C为右边界，以左右边界与出栈柱体B的高度差为深度，计算可以接到雨水的面积，然后记录并更新累积面积

// 左边柱子，离得最近
function trap(height) {
    let ans = 0
    let stack = []
    let size = height.length

    for (let i = 0; i < size; i++) {
        while (stack.length && height[i] > height[stack[stack.length - 1]]) {
            // 如果当前柱体高度较大，大于栈顶柱体的高度，则一直出栈，直到当前柱体小于等于栈顶柱体的高度
            let cur = stack.pop()
            if (stack.length) {
                let left =stack[stack.length - 1] + 1
                let right = i - 1
                let high =Math.min(height[i], height[stack[stack.length - 1]]) - height[cur]
                ans += high * (right - left + 1)
            } else {
                break
            }
        } 
        // 如果当前柱体高度较小，小于等于栈顶柱体的高度，则将当前柱子高度入栈
        stack.push(i)       
    }
    return ans
}

// let height = [0,1,0,2,1,0,1,3,2,1,2,1]
let height = [4,2,0,3,2,5]
console.log(trap(height))